package com.zj.base;

import java.util.Arrays;

/**
 * @program algorithm
 * @description: 插入排序
 * <p>
 * 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * <p>
 * 算法描述
 * 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
 * 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
 * 重复上述过程直到最后一个元素被插入有序子数组中。
 * <p>
 * 稳定性
 * 由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。
 * @author: zhangbo
 * @create: 2022/07/14 02:00
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{7, 5, 8, 9, 1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * {7, 5, 8, 9, 1}
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        int size = arr.length;
        for (int i = 1; i < size; i++) {
            int value = arr[i];
            int position = i;
            while (position > 0 && arr[position - 1] > value) {
                arr[position] = arr[position - 1];
                position--;
            }
            arr[position] = value;
        }
    }


    /**
     * @param: arr
     * @return: void
     * @Description:
     **/
    public static void sort01(int[] arr) {
        int size = arr.length;
        for (int i = 1; i < size; i++) {
            int value = arr[i];
            int position = i;
            while (position > 0 && arr[position - 1] > value) {
                arr[position] = arr[position - 1];
                position--;
            }
            arr[position] = value;
        }
    }
}
